\documentclass{article}

\usepackage{color}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{latexsym}
\usepackage{amsfonts}
%\usepackage{times}
\usepackage{url}
%\usepackage{bibspacing}
%\setlength{\bibspacing}{\baselineskip}
\usepackage{hyperref}
\usepackage{xspace}
\usepackage{graphicx}

\renewcommand{\L}{\mathcal{L}}
\newcommand{\V}{\mathcal{V}}
\renewcommand{\P}{\mathcal{P}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\binary}{\{0,1\}}
\newcommand{\set}[1]{\left\{#1\right\}}

\newtheorem{theorem}{Theorem}[section]

\newcommand{\proref}[1]{Protocol~\protect\ref{#1}}

\newenvironment{boxfig}[2]{\begin{figure}[#1]\fbox{\begin{minipage}{\linewidth}
                        \vspace{0.2em}
                        \makebox[0.025\linewidth]{}
                        \begin{minipage}{0.95\linewidth}
            {\small{
                        #2 }}
                        \end{minipage}
                        \vspace{0.2em}
                        \end{minipage}}}{\end{figure}}


\newcommand{\pprotocol}[5]{
  {\begin{figure}[#4]
      \begin{center}
        \fbox{ \small \hbox{
            \begin{minipage}{.98\linewidth}
              \begin{center}
                \textbf{#1}
              \end{center}
              #5
            \end{minipage}
          } }
        \caption{\label{#3} #2}
      \end{center}
      \vspace{-3ex}
    \end{figure}
} }


\newcommand{\protocol}[4]{
\begin{boxfig}{htbp}{
\begin{center}
{\bf #1}
\end{center}
    #4
\vspace{0.5ex} } \caption{\label{#3} #2}
\end{boxfig}
}


\begin{document}

\section{Correctness of Outsourced Computation}
We consider the settings where a client wants to ``outsource" some computation to an external prover (inspired by cloud computing). The client's resources (time or space) are bounded and it can't perform the computation by itself. We model this by considering a client that can run some fixed polynomial time $p$ (e.g. quadratic). The client wants to evaluate a function $f$ on an input $x$, where the time to compute $f$ is some arbitrary polynomial that might exceed $p$. The server can run arbitrary polynomial time commutations. The client sends to the server its input $x$ and gets back the outcome $z=f(x)$ (the function $f$ is already known to the server).
It is also interesting to consider outsourcing computations that take input from the server as well as from the client. This is modeled by a function $f$ that takes two inputs $x,y$, where $y$ is chosen by the server.

In the cryptographic settings, the client does not trust the server to compute the function correctly. We would like to design a protocol that allows the server to prove to the client that indeed $z=f(x,y)$ for some $y$. Note that when $f$ outputs one bit, the protocol is a general proof system for NP (as long as $|y|$ is polynomial in $|x|$). Our main concern is that the time it takes for the client to verify the proof must not exceed $p$ (the client can't compute $f$ by itself, even if it knows $y$). Such proof systems are called {\em succinct}.

\subsection{The PCP Theorem}
Not surprisingly, succinct proof systems are tightly related to the PCP theorem.
The PCP theorem states that every NP language can also be decided by a ``PCP verifier". Recall that an $NP$ verifier for a language $\L$ is given an instance $x$ and a proof of membership (or a witness) $w$. If $x \in \L$ there exists a proof that makes the verifier accept, and if $x \notin \L$, the verifier will reject every proof. The PCP verifier is similar to the NP verifier except that it is given a proof that is encoded in a special way. This allows the PCP verifier to verify the encoded proof by only reading a few bits of the proof. The PCP verifier uses randomness to select the bit locations it reads and with some small probability (over the verifier randomness), it might accept a proof when $x \notin \L$. For references and historical background on the theorem, see \cite{Dinur07}.

\begin{theorem}[The PCP Theorem]
For every Language in NP $\L$ there exists a probabilistic oracle machine $\V$ (called a ``PCP verifier") such that on input $x$, $|x|=n$, $\V$ uses $O(\log{n})$ random bits, makes $O(1)$ oracle queries and the following holds:
\begin{itemize}
\item If $x \in \L$, there exists $w \in \binary^{\poly(n)}$ such that $\Pr[\V^w(x) = 1] = 1$.
\item If $x \notin \L$, for every $w \in \binary^*$, $\Pr[\V^w(x) = 1] < 1/2$.
\end{itemize}
\end{theorem}
Another important property is that the transformations from an NP witness to a PCP witness and vice versa are explicit and efficient.

Most of the study of PCP systems has been in the context of {\em hardness of approximation} results. For example, consider the following problem: Given a 3-SAT formula $\phi$, let $V(\phi)$ be the maximal fraction of satisfied clauses in $\phi$ over all assignments (if $\phi$ is satisfiable then $V(\phi) = 1$). For some constant $\epsilon$ it is hard to approximate $V(\phi)$ within a factor of $\epsilon$.

This problem can also be stated as a {\em promises problem}: Given a 3-SAT formula $\phi$ such that $V(\phi) = 1$ or $V(\phi) < 1/\epsilon$ for some $\epsilon > 1$ decide which is the case. An alternative formulation of the PCP theorem is that this problem is NP hard (as defined for promises problems) for some constant $\epsilon$. We show that the original formulation of the theorem follows from this one (the other direction is not complicated as well). Given an NP language $\L$ we construct a PCP verifier $\V$ for $\L$ as follows. Given an instance $x \stackrel{?}{\in} \L$ $\V$ reduces it into a 3-SAT formula $\phi_x$ such that $V(\phi_x) = 1$ if $x \in \L$ and $V(\phi) < 1/\epsilon$ if $x \notin \L$ (this is possible since approximating 3-SAT within a factor $\epsilon$ is NP-complete). $\V$ is given oracle access to a proof $w$ that consists of a satisfying assignment of $\phi_x$. $\V$ samples a random clause of $\phi_x$ and queries only the 3 bits of $w$ containing the values assigned to the variables in the clause. $\V$ accepts Iff the clause is satisfied. If $x \in \L$, there is an assignment $w$ that satisfies $\phi_x$ and therefore $\Pr[V^w(\phi_x) = 1]=1$. If $x \notin \L$, every assignment $w$ satisfies at most $1/\epsilon$ of the clauses of $\phi_x$ and therefore $\Pr[V^w(\phi_x) = 1] \leq 1/\epsilon$. By repeating the test independently, constant number of the probability of accepting when $x \notin \L$ in reduced to $<1/2$.

\subsection{Constructing Succinct Proof Systems}
Since a PCP verifier only reads a constant number of proof bits we can try to transform it into a verifier for a succinct proof system. The prover cannot simply send the PCP witness as a proof since the verifier cannot receive it all. Instead, we can have the prover save the PCP witness, and the verifier will send the proof locations it wants to query. The prover will then respond with the corresponding bits of the PCP witness. The problem is that PCP verifier is only guarantied to reject false statements when the witness is fixed independently of the verifier's random coins. Consider for example a cheating prover that receives a random clause from the verifier, and only then selects an assignment that satisfies only this clause.

To solve this problem we use cryptography (CRHF) as well as the power of interaction. The Idea (of \cite{Kilian92}) is to split the proof into 2 rounds (4 messages). In the first round, the prover commits itself to a single PCP proof using a succinct commitment scheme called a hash tree. In the second round, the verifier asks to open some bits of the PCP proof (according to the queries of the PCP verifier) and the prover opens them, showing that they are indeed consistent with the committed proof.

\paragraph{Merkle trees} The prover commits to the PCP proof using a succinct commitment known as {\em Merkle hash tree}. The verifier starts by sending a key to a CRHF that shrinks $2n$ bits to $n$ bits. The prover then splits the PCP proof into blocks of size $2n$ and hashes every block. Joining every pair of adjacent hash values, the prover again creates blocks of size $2n$ and hashes them again in a tree structure until a single hash is obtained. This single hash is known as the root. The prover sends only the root as a commitment to the PCP proof. To open a specific bit of the proof, the prover sends the block that contains the bit and all the hash values on the path from the block to the root (that is, the hash of the block with its sibling block, the hash of the hash with its sibling hash and so on). The prover also sends the sibling block and hashes along the path, allowing the verifier to recompute all the hash values on the path by itself and verify the consistency of the path. The verifier also checks that the last hash in the path is indeed the root sent by the prover in the first round. We rely on two key properties of this construction:
\begin{itemize}
\item Succinctness - while the length of the PCP proof can be an arbitrary polynomial in $n$, the prover commitment is only $n$ bits long (the root). Additionally, to open every bit, the prover sends $2h$ hash values of size $n$, where $h$ is the height of the hash tree. Since the length of the PCP proof is polynomial in $n$, $h = O(\log{n})$. Verifying the consistency of every path can also be done in the time it takes to evaluate the hash $O(\log{n})$ times (this time depends on the hash function and we assume it is less than $p$). Since the verifier only queries $O(\log{n})$ bits of the proof, the total communication complexity of the proof is $\tilde O(n)$.

\item Binding - The CHRF guaranties that the prover is bounded to one PCP proof. That is, the probability that a computationally bounded prover comes up with two different openings for the same bit that are consistent with the same root is negligible. This property is used to show that the proof system is sound (along with the properties of the PCP verifier).

\end{itemize}

The final proof system is as follows:

\protocol {} {Succinct proof system for NP (\cite{Kilian92})}
{kilian.pro} {
\begin{description}
\item[Common Input:] An instance $x \in \L$.
\item[Auxiliary Input to $\P$:] A witness $w$.
\end{description}
\begin{enumerate}
\item
$\V$ sends $\P$ a key $h$ for a CRHF.
\item
Using $w$, $\P$ computes a PCP proof $w'$ for $x \in \L$ and sends the root $r$ of the hash tree of $w'$ using $h$.
\item
$\V$ runs the PCP verifier on $x$ and obtains a list of queries $Q = \set{q_i}$. $\V$ sends $Q$ to $\P$.
\item
For every $q_i \in Q$ the prover sends back the $b_i$, the $q_i$ bit of $w'$, together with proof of consistency $a_i$ of $b_i$ with $r$.
\item
$\V$ verifies that for all $i$, the proof $a_i$ for the consistency of the query-answer pair $(q_i,b_i)$ with the root $r$ is valid. Additionally, $\V$ gives all answers $\set{b_i}$ back to the PCP verifier. $\V$ accepts iff the PCP verifier accepts.
\end{enumerate}
}

\subsection{Succinct Non-interactive Proof Systems in the Random Oracle Model}
It is desirable to have a non-interactive succinct proof system. This will allow us to guarantee the correctness of outsourced computation without increasing the number of rounds: the client sends its input $x$ and the server sends back the result $z = f(x,y)$ together with a non-interactive proof of correctness.

\cite{Micali00} shows how \proref{kilian.pro} can be made completely non-interactive in the presence of a {\em random oracle} $O$. The prover sends the instance $x$ to $O$ and uses the randomness $O(x)$ to sample a hash function $h$. The prover then computes the PCP proof for that statement and $r$, the root of the hash tree of the proof using $h$. The prover sends $r$ to the oracle, and, using the randomness $O(r)$, it runs the PCP verifier itself and obtains the queries $Q$. The prover then generates and answer $a$ as in \proref{kilian.pro}. The final proof consists of the values $r,a$. The verifier, that also has access to $O$, can recompute $h$ and the randomness of the PCP verifier and can then verify that the answers in $a$ are consistent and make the PCP verifier accept.

\subsection{List of Advanced Subjects}
\begin{itemize}
\item
Different delegation protocols for $P$.
\item
Succinct proofs of knowledge and SNARKS.
\item
Construction of SNARKS from knowledge assumptions.
\item
Public vs. private verifiability.
\item
Are PCP's necessary to construct succinct proofs?
\end{itemize}
\bibliographystyle{plain}
\bibliography{crypto}
\end{document}
